//对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。 
//
// 
// 例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。 
// 
//
// 给你一个整数 num ，输出它的补数。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入：num = 5
//输出：2
//解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
// 
//
// 示例 2： 
//
// 
//输入：num = 1
//输出：0
//解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= num < 231 
// 
//
// 
//
// 注意：本题与 1009 https://leetcode-cn.com/problems/complement-of-base-10-integer/ 相
//同 
// Related Topics 位运算 
// 👍 279 👎 0

package com.cute.leetcode.editor.cn;
public class NumberComplement {
    public static void main(String[] args) {
        new NumberComplement().new Solution().findComplement(2);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 这个确实能做出来，但是时间复杂度很不理想，因为是字符串拼接的
         *
         * 1.先对 num 进行「从高到低」的检查，找到最高位 1 的位置 s，然后再对 num进行遍历，将低位到 s 位的位置执行逐位取反操作。
         *
         * 2.通过解法一我们发现，如果 num 的二进制表示中最高位 1 的位置为 s 的话，
         * 那么实际上我们只需要对 num的前 s−1 位进行取反即是答案（第 s 位的取反结果始终为 0）。
         * 因此我们可以先使用 lowbit 操作来得到 num 二进制表示中最高位 1 的位置为 1，其余位为 0 时所代表的数字 x。
         * 然后 x - 1即是二进制表示中前 s - 1位均为 1，其余位为 0 的数字
         * 将其与 num 的取反数执行「按位与」操作，即可达到「仅对 num 的前 s - 1 位进行取反」的效果。
         *
         */
        public int findComplement(int num) {
            /*//题解1，找最高位后遍历取反，md给ans赋值的时候移动的是i而不是ans
            int s = -1;
            for (int i = 31; i >=0 ; i--) {
                if ((num>>i&1)==1){
                    s = i;
                    break;
                }
            }
            int ans = 0;
            for (int i = 0; i < s; i++) {
                //TODO 这里给ans赋值的时候让i进行位移，而不是ans
                if (((num>>i)&1) == 0) ans |= (1<<i);
            }
            return ans;*/

            //题解2.由1可以推广，知道最高位1的位置后，将其剩下的位置按位取反返回就行了
            //所以可以得到最高位为1其他位置为0的数字x，x-1的话就是剩下位置全1，高位为0的数了
            //再将num按位取反并&上x-1的话就是最终结果了
            //说明：i&(-i)是得到最低位的1 然后i-=它之后就是消去一位
            //

            int x = 0;
            for (int i = num; i != 0; i -= i & -i) x = i;
            return ~num & (x - 1);

            /*//我用的字符串拼接的方法，很拉跨的兄弟
           int len = Integer.toBinaryString(num).length();
           StringBuffer s = new StringBuffer();
           for (int i = len-1; i >=0; i--) {
               s.append( ((num>>i)&1) == 1? 0:1);
           }
           return Integer.parseInt(String.valueOf(s), 2);*/

        }
        // 00000101的补数为00000010，所以找到最高位的1之后再找掩码mask，将num^mask即可
        public int findComplement2(int num) {
            if (num == 0) return 1;
            int mask = Integer.highestOneBit(num);
            mask = (mask << 1) - 1;
            return num^mask;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}